#include<bits/stdc++.h>
using namespace std;
#define int long long
#define N 510000
int n,k;
vector<int> g[N];
signed main(){
	freopen("life.in","r",stdin);
	freopen("life.out","w",stdout);
	cin>>n>>k;
	for(int i=1;i<=n;i++){
		int u,v;
		cin>>u>>v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	int flag=1;
	for(int i=1;i<=n;i++){
		flag&=(g[i].size()<=2);
	}
	if(flag){
		cout<<k<<endl;
		return 0;
	}
	return 0;
}